class AbstractDoubleVector
{
public:
    virtual ~AbstractDoubleVector() {}
    virtual double operator[](int i) const = 0;
    virtual void set(int i, double val) = 0;
    virtual void operator*=(double val) = 0;
    virtual void filter(double c, vector<double> &v) const = 0;
    virtual int numNonZero() const = 0;
};

class DenseDoubleVector : public AbstractDoubleVector
{
public:
    DenseDoubleVector(int size) : _data(size) {}
    double operator[](int i) const { return _data[i]; }
    void set(int i, double val) { _data[i] = val; }
    void operator*=(double val)
    {
        for (UINT i = 0; i < _data.size(); i++) {
            _data[i] *= val;
            if (-0.01 < _data[i] && _data[i] < 0.01) _data[i] = 0;
        }
    }
    void filter(double c, vector<double> &v) const
    {
        for (UINT i = 0; i < v.size(); i++) v[i] += c * _data[i];
    }
    int numNonZero() const
    {
        int num = 0;
        for (UINT i = 0; i < _data.size(); i++) if (_data[i] != 0) num++;
        return num;
    }
private:
    vector<double> _data;
};

class SparseDoubleVector : public AbstractDoubleVector
{
public:
    SparseDoubleVector() : _epsilon(0.01) {}
    SparseDoubleVector(double epsilon) : _epsilon(epsilon) {}

    double operator[](int i) const;
    void print() const;
    void set(int i, double val);
    void operator*=(double val);

    // Remove all elements of magnitude < epsilon
    void cleanup(double epsilon);

    // Equivalent to v += c * this
    void filter(double c, vector<double> &v) const;

    // Number of nonzero elements
    int numNonZero() const { return _data.size(); }

private:
    std::map<int, double> _data;
    double _epsilon;
};

void testSparseDoubleVector();